#include <iostream>
#include <stack>
using namespace std;
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right) {
    int temp = a[left];
    int l = left;
    int r = right;
    while(true) {
        while(a[l] < temp) l++;
        while(a[r] > temp) r--;
        if(l >= r) {
            return r;
        }
        swap(a[l], a[r]);
        l++;
        r--;
    }
    
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right) {
    int temp = a[left]; // 挖坑
    int l = left;
    int r = right;
    while(l < r) {
        while(l < r && (a[r] >= temp)) { // 这里不能互换循环顺序，谁挖的坑，让对方填
            r--;
        }
        if(l < r) {
            a[l++] = a[r];
        }
        while(l < r && (a[l] <= temp)) {
            l++;
        }
        if(l < r) {
            a[r--] = a[l];
        }
    }
    a[l] = temp;
    return r;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right) {
    int temp = a[left];
    int index = left;
    for(int i = left + 1; i <= right; i++) {
        if(a[i] < temp) {
            index++;
            swap(a[index], a[i]);
        }
    }
    swap(a[index], a[left]);
    return index;
}
void QuickSort(int* a, int left, int right) {
    // if(left < right) {
    //     int mid = PartSort1(a, left, right);
    //     QuickSort(a, left, mid);
    //     QuickSort(a, mid + 1, right);
    // }
    // if(left < right) {
    //     int mid = PartSort2(a, left, right);
    //     QuickSort(a, left, mid);
    //     QuickSort(a, mid + 1, right);
    // }
    if(left < right) {
        int mid = PartSort3(a, left, right);
        QuickSort(a, left, mid);
        QuickSort(a, mid + 1, right);
    }
}

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {
    if(left >= right) return;
    stack<pair<int, int>> st;
    st.push({left, right});
    while(!st.empty()) { // 模拟栈的调用过程
        auto&[l, r] = st.top();
        st.pop();
        if(l >= r) continue;
        int mid = PartSort3(a, l, r);
         // ⚠️ 注意：先压右，再压左
        st.push({mid + 1, r}); // 右区间
        st.push({l, mid});     // 左区间
    }
}
int main() {
    int a[10] = {1, 4, 3, 5, 6, 3, 2, 7, 8, 0};
    QuickSort(a, 0, 9);
    for(int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}